AUTHORS: Dimitris Varsamis, Fotios Chanlioglou
Download as PDF
ABSTRACT: : In this work we introduce a parallel approach of Best Fit Decreasing algorithm. The Best Fit Decreasing algorithm is heuristic and is used for optimal assignment problems, for example cutting stock problem, bin packing problem etc. The above problems for optimal assignment have very large computational complexity. For this reason have developed heuristic algorithms which aim at the reduction of computational time with disadvantage on solution. The Best Fit Decreasing compute, in most times, a approach of optimal solution. The purpose of the study is twofold: (a) to split the dataset of problem with representative manner so that at every sub-problem to Best Fit Decreasing algorithm is applied and the cost to the results to be the smallest and (b) to be implemented program in Matlab that will running every sub-problem with parallel techniques with the aim of reducing computational time
KEYWORDS: Linear Programming, Optimization, Bin Packing Problem, Parallel Processing
REFERENCES:
[1] M. R. Garey, D. S. Johnson, Computers and Intractability; A Guide to the Theory of NPCompleteness, W. H. Freeman & Co., New York, NY, USA, 1990.
[2] R. E. Korf, A New Algorithm for Optimal Bin Packing, Eighteenth National Conference on Artificial Intelligence, Edmonton, Alberta, Canada, (2012), 731-736.
[3] A. N. Zehmakan, Bin Packing Problem: Two Approximation Algorithms, CoRR, (2015), abs/1508.01376
[4] D. S. Johnson, A. J. Demers, J. D. Ullman, M. R. Garey, R. L. Graham, Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms, SIAM J. Comput., 4 (1974), 299- 325.
[5] P. Luszczek, Parallel Programming in MATLAB, International Journal of High Performance Computing Applications, 23 (2009), no. 3, 277-283.
[6] C. Moler, Parallel MATLAB: Multiple processors and multiple cores, The MathWorks News & Notes, (2007).
[7] G. Sharma, J. Martin, MATLAB : A Language for Parallel Computing, International Journal of Parallel Programming, 37 (2009), no. 1, 3-36.
[8] D. N. Varsamis, C. Talagkozis, P. A. Mastorocostas, E. Outsios, N. P. Karampetakis, The performance of the MATLAB Parallel Computing Toolbox in specific problems, Federated Conference on Computer Science and Information Systems (FedCSIS), Wroclaw, Poland, (2012), 587- 593.
[9] D. N. Varsamis, P. A. Mastorocostas, A. K. Papakonstantinou, N. P. Karampetakis, A parallel searching algorithm for the insetting procedure in Matlab Parallel Toolbox, Advanced Information Science and Applications Volume I, 18th Int. Conf. on Circuits, Systems, Communications and Computers (CSCC 2014), July 17-21, 2014, Santorini Island, Greece, (2014), 145-150.
